#The TSP problem
#created by logan rooper- Riverdale High School - logan.rooper@gmail.com
#Random walk
import random
import math

################################################################################################
cycles = int(input("How many iterations do you want? >")) #INCREASE THIS TO INCREASE ITERATIONS#
num_cities = int(input("How many cites do you want? >")) #SET NUMBER OF CITIES                 #
################################################################################################

#Setting up the problem
print("Setting up the problem")
cities=[] #the regular city map
h_cities=[] #the highscore city map

#Generate num_cities random cities
#Cities should be in a X by Y array (0-9 coordinates
#Coordinates can be 101 through 199 (1 is the octal padding bit)
print("There are "+str(len(cities))+" cities.")

cities=(random.sample(range(100,199), num_cities))
for x in range(0,num_cities):
    print("Making city "+str(x)+".")
    print("City "+str(x)+" is X: "+str(cities[x])[2]+" and Y:"+str(cities[x])[1])

print("There are now "+str(len(cities))+" cities.")

#draw city map
print("PRINT MAP")
print("--> X axis")  
print("|")		
print("| Y axis")		
print("V")
#iterate through all coordinates
row = ""
count = 1
for z in range(100,199):
    if z in cities:
        row += "--*--|"
    else:
        row += "-----|"
    if count == 10:                #rows is the width of the map...unsused because of our integer data limits
        row += "\n"
        count = 0
    count += 1

print(row)
        

print("Ready to create and run the algorithm??")
i = input(">")

#Create and run the algorithm
print("Creating/running the algorithm.")
high = 10000000.0 #arbitrarily high float value
done = False
i = 0
while (done != True):
    print("Starting iteration "+str(i))

    ########ALGORITHM START##########
    #create a list of paths (a generation)
    generation = []
    mid = []
    sub = []
    '''GENERATION STRUCTURE  
                 
    generation[member_number] --> mid[0,1] --> sub[0xy]
                                               fitness
                 &calling member's fitness is
                     generation[member_number][1]
                 &a member's path item is
                     generation[member_number][0][i]
    '''
    #populate first generation with 50 random induviduals
    for x in range(0,50):
        generation = []
        mid = []
        sub = []
        #shuffle the member
        member[] = random.shuffle(cities)
        #add the member's path to mid
        mid.insert(0,member)
        #calculate the member's fitness
        distance = 0
        for index, city in enumerate(member):
            cx = int(str(city)[1]) #currentX
            cy = int(str(city)[2]) #currentY
            if index != 0:
                #measure the absolute distance between c* and p* if it's not the first city
                distance += math.sqrt(abs((cx-px))**2+abs((cy-py))**2)
            px = cx
            py = cy
        
        fitness = 10/distance
        #add the member's fitness to mid
        mid.insert(1,fitness)
        #push the member (mid) to generation
        generation.append(mid)
    #
    mid.insert(0,sub)
    generation.insert(x,mid)
    
    #########ALGORITHM END###########
    
    if distance < high:
        high = distance
        h_cities = cities
        print("NEW HIGHSCORE FOUND ------------")
        print(repr(h_cities))
    i += 1
    if i >= cycles:
        done = True
print()
print("Shortest path found was "+str(high)+" units long.")

print("PRINT MAP") #map of h_cities
print("--> X axis")  
print("|")		
print("| Y axis")		
print("V")
row = ""
count = 1
for z in range(100,199):
    if z in h_cities:
        if cities.index(z) < 10:
            cit = "0"+str(cities.index(z))
        else:
            cit = str(cities.index(z))
        row += "--"+cit+"-"
    else:
        row += "-----"
    if count == 10:
        row += "\n"
        count = 0
    count += 1

print(row)

#EOF

